Since methods based on linked list in existing microscopic traffic simulation systems are not efficient and scalable to process Nearest Neighbor (NN) queries, a variation of B+ tree based method was proposed to resolve these problems. This method combined ideas from NN queries in database with advantages of linked list. By maintaining indices of nearby vehicles of each vehicle in the local lane, the performance of NN queries in that lane could be largely improved. Under the assumption of randomly distribution of vehicles, a mathematical model was also proposed to optimize the parameter setting according to multiple parameters for lanes and the amount of vehicles. This model calculated the minimized average query length of each NN query to optimize the parameter setting. The results of theoretical analysis and simulations showed that in common traffic conditions including sparse, normal and congestion, the main indicator, namely the average simulation time cost of each vehicle, could be reduced by 64.2% and 12.8% compared with linked list and B+ tree respectively. The results prove that the proposed method is suitable for larges-cale microscopic traffic simulation systems.